#include "disjoint-set.h"

void DisjointSet::djs_union(int x, int y) {
    int s1 = find(x);
    int s2 = find(y);
    if(s1 == s2) return;
    if(parent[s1]<parent[s2]) { //s1的rank或size比s2的大
        if(bs) parent[s1] += parent[s2]; 
        parent[s2] = s1;
    }else {
        if(bs) parent[s2] += parent[s1];
        else if( parent[s1]==parent[s2]) //两者rank相同，合并后的树的rank增加1
            parent[s2] += -1;
        parent[s1] = s2;
    }
}

int DisjointSet::find(int x) {
    if(parent[x]>=0) { 
        //这里采用路径压缩，使得递归在返回时，将所有非根结点的父结点均指向根
        parent[x] = find(parent[x]);
        return parent[x];
    }
    return x;
}

